/**
 * 2016年10月2日
 */
package algorithm;

import java.util.Arrays;

/**
 * @author Alex
 *
 */
public class Quick {
	public static void main(String args[]){
		int t[] = {5,4,3,2,1};
		new Quick().sort(t,0,t.length-1);
		System.out.println(Arrays.toString(t));
	}
	public void sort(int arr[] ,int s,int e){
		if(s<e){
			int mid = partition(arr, s, e);
			sort(arr,s,mid-1);
			sort(arr,mid+1,e);
		}
	}
	
	public int partition(int arr[],int start,int end){
		int temp = arr[start];
		while(start<end){
			while(start<end && arr[end]>=temp){
				end--;
			}
			if(start<end){
				arr[start++] = arr[end];
			}
			
			while(start<end && arr[start]<=temp){
				start++;
			}
			if(start<end){
				arr[end--] = arr[start];
			}
		}
		arr[start] = temp;
		return start;
	}
	public void swap(int arr[],int idx1,int idx2){
		int temp = arr[idx1];
		arr[idx1] = arr[idx2];
		arr[idx2] = temp;
	}
	
}
